This relates to a massively parallel processor having a large number of interconnected processors operating in parallel and, in particular, to one in which such processors are interconnected in a hyper-dimensional pattern (i.e., a pattern of more than three dimensions). Advantageously, the processors are connected in a Boolean n-cube where n is relatively large (e.g. n.gtoreq.10).
As described in connection with FIG. 1A of the above-reference applications, an array 30 of parallel processing integrated circuits (ICs) 35, illustratively, contains 32,768 (=2.sup.15) identical ICs 35; and each IC 35 contains 32 (=2.sup.5) identical processor/memories 36. Thus the entire array 30 contains 1,048,576 (=2.sup.20) identical processor/memories 36. Processor/memories 36 are organized and interconnected in two geometries. The first is a conventional two-dimensional grid pattern in which the processor/memories are organized in a square array and connected to their four nearest neighbors in the array. The second is a Boolean n-cube of fifteen dimensions.
The present invention is related to the realization of the second of these interconnection geometries in the three-dimensional world of integrated circuits, circuit boards and backplanes (or mother boards) in which it must be built.
To understand the n-cube connection pattern for ICs 35, it is helpful to number the ICs from 0 to 32,767 and to express these numbers or addresses in binary notation using fifteen binary digits as in Table I.
TABLE I ______________________________________ IC address IC address in decimal in binary notation notation ______________________________________ 0 000 000 000 000 000 1 000 000 000 000 001 2 000 000 000 000 010 3 000 000 000 000 011 4 000 000 000 000 100 . . . . . . . . . . . . . . . . . . 32765 111 111 111 111 101 32766 111 111 111 111 110 32,767 111 111 111 111 111 ______________________________________
Just as we can specify the position of an object in a two dimensional grid by using two numbers, one of which specifies its position in the first dimension of the two-dimensional grid and the other which specifies its position in the second dimension, so too wee can use a number to identify the position of an IC in each of the fifteen dimensions of the Boolean 15-cube. In an n-cube, however, an IC can have one of only two different positions, 0 and 1, in each dimension. Thus, the fifteen-digit IC address in binary notation as set forth in Table I also specifies the IC's position in the fifteen dimensions of the n-cube. For convenience, we will use the left-hand-most digit of the fifteen binary digits to specify the IC's position in the first dimension, and so on in order to the right-hand-most digit which specifies the IC's position in the fifteenth dimension.
Moreover, because a binary digit can have only two values, zero or one, and because each IC is identified uniquely by fifteen binary digits, each IC has fifteen other ICs whose binary address differs by only one digit from its own address. We will refer to these fifteen ICs whose address differs by only one from that of a first IC as the first IC's nearest neighbors. Those familiar with the mathematical definition of a Hamming distance will recognize that the first IC is separated from each of its fifteen nearest neighbors by the Hamming distance one. Two examples of the addresses of an IC and its fifteen nearest neighbors are set forth in Table II of the above referenced applications. With reference to Table I of the present application, the ICs whose decimal address are 1, 2 and 4 are some of the nearest neighbors of the IC whose decimal address is 0.
To connect ICs 35 of the above-referenced applications in the form of a Boolean 15-cube, each IC is connected to its fifteen nearest neighbors by 15 input lines 38 and fifteen output lines 39. Each of these fifteen input lines 38 to each IC 35 is associated with a different one of the fifteen dimensions of the Boolean 15-cube and likewise each of the fifteen output lines 39 from each IC 35 is associated with a different dimension.
To permit communication through the interconnection pattern of the Boolean 15-cube, the results of computations are organized in the form of message packets; and these packets are routed from one IC to the next by routing circuitry in each IC in accordance with address information that is part of the packet. An illustrative format of the message packet is depicted in FIG. 4 of the above-identified applications where it is seen to comprise fifteen bits of IC address, a format bit, another fifteen bits duplicating the IC address, five bits of address to the processor/memory in the IC, four bits of address to a register in the processor/memory, thirty-two bits of a message and one bit for error detection. Alternatively, a message packet can be used that employs only one set of fifteen bits for an IC address.
In the message packet, the IC address information is relative to the address of the destination IC. Initially, it is the difference or the displacement between the address of the IC that is the source of the message and that of its destination. For example, if the address of the source IC is 010 101 010 101 010 and the address of the destination IC is 111 111 111 111 111, then the relative address that is generated at the source IC is 101 010 101 010 101. It will be apparent that 1-bits in the relative address identify the dimensions where the message packet is not in the correct position and therefore identify the dimensions through which the message packet must be moved to reach the destination IC. Thus, in the above example, where the addresses of the source and destination ICs are the same in each of the even-numbered dimensions, the message is already located in the proper position in those dimensions. However, in the odd dimensions where the addresses of the source and the destination ICs are different, the presence of 1-bits in the relative address for those dimensions indicates that it is necessary to move the message packet from one IC to another in that dimension.
As the message is routed from one IC to the next, the relative address is updated to take into account each move. In the case where the message packet includes a duplicate IC address, this is conveniently done by complementing the bits in the duplicate IC address that are associated with the dimensions through which the message packet is moved. As a result, when the message packet arrives at the destination IC, the bits in the duplicate IC address will be all zeros.
The routing circuitry in all the ICs is identical and operates in synchronism using the same routing cycle. In the first time period of each routing cycle, the routing circuitry at each IC in the Boolean n-cube tests the leading bit of the first copy of the IC address of each message packet in the routing circuitry to determine its level. If there is a 1-bit in this position and if the output line from that IC which is associated with the first dimension is not already busy, the message packet is routed down the first dimension output line to the IC's nearest neighbor in the first dimension. If the leading bit of the message packet address is a 0-bit, the message packet remains in the same IC because it is in the correct position in the first dimension.
The leading bit of the first copy of the IC address in the message packet is then discarded. If the message packet was routed to another IC, the corresponding address bit in the duplicate IC address is complemented in order to account for such move.
In the second address time period, the routing circuitry of each IC tests the second bit of the relative address which indicates whether the message packet is in the proper position in the second dimension. If the bit is a 1-bit and if the second dimension output line is not already busy, the message packet is then routed out on the second dimension output line to that IC's nearest neighbor in the second dimension. If the bit is a 0-bit, the message packet remains in the IC.
This process continues through fifteen address time periods, at the end of which each of the fifteen address bits of the message packet will have been tested; and if the needed output lines were available, a path will have been established through the Boolean 15-cube through which the remainder of the message packet can be transmitted.
In the case where the message packet contains only a single fifteen-bit IC address, the process is the same, but the bits of the IC address are not discarded after use in routing selection. Rather, the bit associated with each dimension is complemented if the message packet was routed to another IC in that dimension and the entire address, as complemented, is retained. Again, when all fifteen bits of address are zero, the message packet has reached its destination.